量子计算论文精讲《基于Rydberg原子阵列的最大独立集量子优化问题》

欢迎大家扫码关注MindSpore Quantum Gitee社区

内容简介

实现量子加速，以解决实际相关的、计算困难的问题是量子信息科学的一个核心挑战。近年来，全球掀起了中性原子系统的研究热潮，越来越多的公司热衷于发展这项技术。本次报告，将介绍三篇中性原子量子优化算法方面的文章，其中第一篇文章主要关注在里德伯格原子阵列中研究求解最大独立集问题的量子算法，通过对比量子算法和经典的退火算法，发现了在深层线路中寻找精确解的超线性量子加速现象。第二篇文章分析了量子绝热优化算法在具有平坦低能景观的难问题上相比于经典退火算法具有根号加速的条件。第三篇文章提出两种方法绕过当间隙很小时量子绝热算法演化时间超指数大的问题。

相关论文1

标题：Quantum optimization of maximum independent set using Rydberg atom arrays
作者：S. Ebadi, A. Keesling, M. Cain, T. T. Wang, H. Levine, D. Bluvstein, G. Semeghini, A. Omran J.-G. Liu, R. Samajdar, X.-Z. Luo, B. Nash, X. Gao, B. Barak, E. Farhi,S. Sachdev, N. Gemelke, L. Zhou, S. Choi, H. Pichler, S.-T. Wang, M. Greiner,V. Vuletić, M. D. Lukin
期刊：Science 376, 1209–1215 (2022)

相关论文2

标题：Quantum speedup for combinatorial optimization with flat energy landscapes
作者：M. Cain, S. Chattopadhyay, J.-G. Liu, R. Samajdar, H. Pichler, M. D. Lukin
arXiv：2306.13123v2（2023）

相关论文3

标题：Circumventing superexponential runtimes for hard instances of quantum adiabatic optimization

作者：Benjamin F. Schiffer, Dominik S. Wild, Nishad Maskara, Madelyn Cain, Mikhail D. Lukin, and Rhine Samajdar

arXiv：2306.13131v1（2023）

01

中性原子量子计算

图1 中性原子阵列量子比特（来源：https://physics.aps.org/articles/v15/s55）

1.1 中性原子阵列

从2021年开始，中性原子量子计算系统成为了研究学者关注的热门，中性原子量子计算的发展主要因为光镊技术的发展，使得我们可以对多个冷原子进行操控，以及两比特操作也可以高保真度的实现。中性原子量子系统的可扩展好，可以在一两年的时间之内扩展到100-1000个量子比特。此外，它相比于超导量子系统也有着更好的连接性，超导量子系统中一个量子比特只能和近邻量子比特存在相互作用，但是中性原子系统中的一个量子比特可以近邻，次近邻等量子比特同时存在相互作用。中性原子阵列在数字计算中使用基态的超精细能级分别编码|0⟩和|1⟩，而在模拟计算中，一般使用基态编码|0⟩，里德堡态编码|1⟩，通过选择不同能级的量子态来编码，可以模拟多种模型。

1.2 数字计算

中性原子系统计算的原理是用激光控制冷原子进行演化，激光驱动的哈密顿量可以表示为：

因此，如果激光只聚焦到一个原子上控制其演化，因为数字计算中原子都是处于基态，它们的相互作用很弱，可以忽略,所以。因此根据薛定谔方程，我们可以得到原子的末态表示为

所以，仅需要控制驱动光场的拉比频率,相位以及失谐和演化时间，就可以实现任意的单量子比特门。

想要实现通用的量子计算，多比特门是必不可少的，在中性原子量子系统中如何实现多比特量子门？首先，激光驱动冷原子的哈密顿量中没有两个原子的相互作用项，但是多比特门的实现至少也需要CNOT门和任意的单量子比特门。在光子系统中，两个光子之间没有相互作用，因此如果要实现CNOT门，只能通过后选择的方法或者提前产生纠缠态的方法。

在中性原子系统中，两个基态的原子的相互作用也非常的微弱，但是当两个原子都处于里德堡激发态时，它们的相互作用相比于两个基态的相互作用会提升~12个数量级，因此通过这个相互作用可以产生纠缠关系。

图2 里德堡阻塞作用（来源：https://doi.org/10.1038/s41586-022-04603-6 ）

这种非常强的里德堡相互作用使得CZ门非常容易实现。虽然量子比特是在基态的超精细能级上编码，但是在演化的过程中，我们可以借助里德堡激发态作为中间态。

如图3（a）所示，当考虑输入态为|00⟩时，第一步对控制量子比特的这个原子输入一个能量合适的pi脉冲，这个脉冲可以将|0⟩态的原子激发到里德堡态，此时两量子比特态变为

,第二步是对目标量子比特这个原子输入一个能量不变的2pi脉冲，如果两个原子之间没有相互作用，那么目标量子比特对应的原子应该会跃迁到里德堡态然后回到原来的位置，整体相当于加上一个 的相对相位，但是实际上因为里德堡阻塞作用，目标量子比特对应的原子并不会发生跃迁，而是待在原来的位置不会改变，第三步是对控制量子比特对应的原子输入能量不变的pi脉冲，该原子会因为受激辐射回到态，因此最后的两量子比特为-1|00⟩。

在图3（b-d）中，处于|1⟩态的原子收到激光的照射，因为失谐的存在，并不会发生跃迁，因此两个原子的初态|01⟩会变为末态-|01⟩，初态|10⟩会变为末态-|10⟩,初态|11⟩会变为末态|11⟩。因此，如图3（e）中的两束激光按照上面的三个步骤分别照射到两个原子上，通过上面所述的三个步骤就可以实现CZ门。想要实现CNOT门仅需要额外的两个单比特H门就可以。

图3 CZ门的产生（ 来源：https://pennylane.ai/qml/demos/tutorial_neutral_atoms）

1.3 模拟计算

数字计算中想要分解任意的线路，就需要实现各种复杂的光脉冲调控操作，目前还存在一定的困难。在目前的阶段，对于原子阵列实现全局的光调控是较容易实现的。在模拟计算中，只需要对全局光的振幅，频率，相位实现调控，就可以控制原子阵列的演化。

图4 模拟计算（来源：https://doi.org/10.1038/s41586-022-04603-6 ）

当选择基态和里德堡态进行编码时，原子阵列演化的哈密顿量可以表示为：

当选择两个不同的合适的里德堡态进行编码时，原子阵列演化的哈密顿量可以表示为：

后边的这种模型第三项表示和的相干转换，因为它们的能量相同，所以量子态会在它们之间不断转换。

02

基于中性原子系统解决MIS问题

2.1 最大独立集（Maximal Independent Set, MIS）问题

给定无向图G=(V,E)，找到最大节点子集U，使得U中的任意两点之间都没有边相连。一般来说，求解最大独立集的问题基本等价与判断无向图是否存在独立集，其中的顶点数量M大于等于某一个常数k。

图5 最大独立集问题（Science 376, 1209 (2022)）

2.2 问题难度已经有理论证明判断最大度为3的平面图是否满足是一个NP完全问题。在中性原子系统中，因为近邻原子的里德堡阻塞作用，因此在里德堡半径范围内的原子将不会同时被激发，这个物理现象对应单位盘图上的最大独立集问题。

图6 原子阵列中的单位盘图的最大独立集求解

对于任意的最大度为3的平面图，可以将其映射到原子阵列的单位圆盘图上。映射的方法如图7所示。

图7 最大度为3的图映射到原子阵列的单位圆盘图（来源：Science 376, 1209 (2022)）

G=(V,E)图可以放到一个方格图中，然后其每一条边都可以被G'=(V',E')中的个点代替，这样就保证了原图中的相连的两个点具有阻塞作用。这种变换将具有N个顶点和最大度3的平面图映射到具有多项式顶点数的方格上的单位磁盘图，并且这种映射可以在顶点数的时间多项式中有效地生成。格点图中邻近和次邻近的点存在相邻的边，对于这种图的MIS问题求解是NP完全的。只存在邻近边的话不是NP完全的。在变换的过程中，需要保证辅助点的个数是偶数个，保证传递规律的正确性，而且每一条辅助线不相交。可以证明，映射之后的最大集的求解问题变为。

2.3 实验数据的处理

因为噪声的存在，需要对实验数据进行预处理。预处理中较为关键的两个步骤分别是删除顶点和添加顶点。

图8 删除顶点和添加顶点（图a来源：Science 376, 1209 (2022)）

删除顶点：该过程从计算每个顶点的封锁违规数开始。违反次数最多的顶点将被删除（从翻转到  。重复计算违反封锁并删除最差顶点的过程，直到没有再违反的顶点。添加顶点：因为误差和删除过程的存在，得到的结果不是极大独立集，因此，可以使用恒定开销贪婪算法来使独立集最大化（直到在不违反封锁的情况下不能添加更多的顶点）。

对实验数据的预处理是非常有效的。图9A展示了179原子中里德伯格激发数的直方图（红线显示最大独立集的大小）。B是删除Rydberg封锁违规后处理后的直方图。近似比定义为，其中表示单次实验的激发原子的数量，是理论的最大独立集的值。是分布的排除长尾时的平均近似比。是多次重复实验之后解为最大独立集的概率。C是添加顶点后处理后的直方图，使输出独立集最大。D展示了顶点约简后的独立集大小与后处理前的Rydberg激励数量的关系。每个点到黑色虚线的水平距离指示减小的幅度。蓝色虚线表示最大独立集的确切大小。E展示了顶点添加后与顶点添加前的独立集大小，每个点到黑色虚线的垂直距离表示添加原子的多少。

图9 实验数据预处理的效果（来源：Science 376, 1209 (2022)）

2.4 量子近似优化算法（Quantum approximate optimization algorithm，QAOA）

标准的量子近似优化算法可以被p层参数化的时间演化完成，通过两个不对易的算符和，量子态的演化过程可以表示为

一般来说，一个组合优化问题可以编码在损失函数哈密顿量上。系统的初态一般从哈密顿量的基态开始，目标是使用变分的2p层的两组参数找到一个量子态使得损失函数尽可能小，即。

图10 在中性原子量子系统的量子近似优化算法（来源：Science 376, 1209 (2022)）

依据之前的讨论,可以取

在求解MIS问题的时候，因为里德堡阻塞作用，量子态被局域在独立集对应的量子态中演化。因此，这两个公式可以重新被表示为

其中是将量子态投影到独立集子空间的算符。进行简化之后可以重新计算量子态的演化为

在实验中，取

2.5 变分量子退火算法（Variational Quantum Adiabatic Algorithm，VQAA）

变分量子退火算法的目的是找到一条最优的准绝热路径，该路径是初态哈密顿量和感兴趣问题的结果的基态哈密顿量中间的插值。在作者的实验中，失谐量随着时间从负值变化到正值，拉比振荡频率保持为一个常数。失谐量被参数化为一些分段函数，初始的失谐量为，总的失谐量有每一段的持续时间，和终点决定。耦合的失谐量首先花费的时间线性的从0拉升到，并且同样的在结束的时候用相同的时间下降回去。和一起抑制哈密顿量的急剧变化。所以在量子绝热演化中设计到的变分参数总共有个。

图11 变分量子退火算法（来源：Science 376, 1209 (2022)）

失谐量可以分为f个时间相关的分段线性函数，有效层数定义为失谐量变化的持续时间以脉冲持续时间为单位的值。作者他们发现只有三段的失谐函数在有效层数的时候变分量子退化算法的效果好于QAOA，此外，通过图11D也可以发现三段的失谐函数（橙色点线）相比于一段的失谐函数（蓝色点线）效果也要好一些。

将失谐函数拆解为更多段的实现可以得到和3段失谐函数类似的曲线，因此意义不大。如果有效层数设置得比较大，比如，可以从图11D观察到结果会更差，这是因为系统演化的时间过长，已经发生了退相干。

2.6 实验结果

作者选择SA进行基准测试，因为它与所使用的量子算法类似，是一种通用算法，只依赖于成本哈密顿量的信息来解决这个问题。退火步骤深度定义为在每一个spin上的平均更新次数。使用1-R和作为目标函数分别对比量子算法和SA算法的效果。定义难度参数，这个参数表示次优解的简并情况，这个参数的值越大，意味着次优解简并度相比于最优解简并度越大，对于最优解的寻找越困难。定义参数，表示最优解的简并度的对数除以图的大小。

分别使用量子算法和SA算法对80个顶点的图分别进行求解，在图12A中，绿色和灰色的图是较为容易求解的，与之相反的是，当图的次优解简并很大时，如紫色和金色的图就相对难以求解，并且最后的R值限于。图12B和C展示了困难图中金色对应的的图相比于紫色对应的图，解的汉明距离和最大解的概率收敛的速度更快，但是对于SA算法这两个图的求解表现基本类似。图12D展示了39个顶点的图，困难系数，其中，如果两个设置可以通过一个模拟退火步骤分离，则使用一条边连接。在图12E中，36张不同难度的图，使用32层的线路深度进行求解。当满足关系时，其中是最小能级差，那么排除图中中空的点，量子算法可以得到更好的scaling。

图12 量子算法和经典退火算法的对比（来源：Science 376, 1209 (2022)）

03

平坦能量景观组合优化的量子加速

3.1 SA算法的时间尺度

SA运行时主要是克服平坦的能量环境,一般来说，经典SA算法求解的时间下限和最小能级间隙的关系为

通过计算可以将表示为

实验上测得的实际时间与理论分析的时间下界线性相关，相关系数为3/4。

图13 平坦的能量决定SA运行时间（来源：arXiv:2306.13123v2）

3.2 QAA算法的时间尺度

假设拉比频率和失谐量被最优设置，使得演化时间最少，此时QAA算法的的运行时间具有关系

最小能级间隙取决于最优解和次优解的形式。考虑三种不同性质的最优解量子态和次优解量子态，他们分别是非局域，受欢迎的局域和不受欢迎的局域。

最优解对应的量子态和次优解对应的量子态可以分别表示为

最小能级间隙可以用下式进行估算

其中

对于来说，（对应上文的）将会产生个自旋翻转去连接和的配置。

最小能级间隙的值和最优解对应的量子态以及次优解对应的量子态的振幅系数密切相关，当振幅系数和几乎均匀分布时，如图18c所示，此时量子态可以表示为

其中

对于这种非局域情况，次优解附近总能够通过翻转1个自旋比特找到最优解，因此可以取，因此，最小间隙能量的估算可以表示为

因此可以发现，QAA算法相比于SA算法具有二次加速的效果，这种加速效果和Grover算法类似。但是实际上，因为最优解的搜索总是在次优解的附近快速得到，因此实际上的搜索速度会比Grover算法更快。

但是当给定的求解图如图12d所示的时候，当分支数大于2，此时次优解将会陷入一种局域的状态。如果次优解与最优解的汉明距离比较近，那么这种局域仍然是受欢迎的，在这种情况下，

此时，QAA算法相较于SA算法还是存在比较大的优势。但是当次优解与最优解的汉明距离非常远的时候，这种情况使用QAA算法就有点“大海捞针”的感觉，尤其是次优解的简并度远超过最优解的简并度的时候，此时QAA算法很难将量子态演化到最优解，这种情况称为不受欢迎的局域。

图14 本征态的位置决定了QAA的运行时间（来源：arXiv:2306.13123v2）

定量来说，考虑星性图局域情况的简并，当增加时，每一条分支的简并度为

所以，对于条分支的图，简并度为

 图15 次优解简并随着size增加的拓展展示，每一条边除了中心点的点的数量为偶数个

因此，经典的SA算法的运行时间关于分支数成指数增长

使用二阶微扰的方法取计算QAA的运行时间，首先可以估算出最小能级间隙为

可以看出，当很大的时候，，因此

3.3 改进的QAA算法

在上面所述的内容中可以看到，对于高简并，且简并态次优解的量子态与最优解的量子态的汉明距离很远的情况下，QAA算法相较于经典的SA算法不仅没有加速效果，反而存在减速。如果能优化QAA算法，将本征态去局域化，那么QAA算法应该会表现得更好。

设计新的哈密顿量为

其中，新加入的哈密顿量受到单粒子动能算子的启发，这个算符的本征态是均匀分布的。修改好的哈密顿量的对于次优解的量子态能量和最优解的量子态能量差将会缩小到根号简并值之比的关系，因此，此时的QAA相比于经典的SA算法会具有根号加速的效果。这个算符可以根据图进行设计，这篇文章使用单位圆盘图对应的离散拉普拉斯算子

如图26c所示，对于720个顶点的单位圆盘图，QAA算法具有根号加速的效果，且的时候效果最好。对于上一小节中的星形图，QAA算法同样具有根号加速的效果。

图16 改进QAA算法的量子加速（来源：arXiv:2306.13123v2）

需要注意的是，QAA算法相比于量子蒙特卡罗算法（模拟量子退火算法）仍然有根号加速的效果。

3.4 如何理解量子加速

图17 实验表现分析(a)进化时间太短的实例偏离了绝热演化的趋势;(b)在量子次优解局域的情况中，QAA实验的求解时间小于SA算法的时间，在非局域的情况中，实验上的QAA计算时间具有根号加速;(c)三种不同局域的图的次优解和最优解的汉明距离分布。（来源：arXiv:2306.13123v2）

在2022年Science发表的工作中，作者所在的实验组观察到对于次优解简并远大于最优解简并的难图中，QAA算法相比于SA算法可以观察到一些优势。在实验中，实验上的得到的计算结果的时间为

其中是QAA在T时间内求得最优解的概率。图17a展示了实验上的最优求解时间和理论计算时间的区别，可以发现两者基本上是线性相关的。在图17b中，可以看到实验上求解的时间和经典的SA时间不存在绝对的线性关系，当次优解的态空间比较接近均匀分布的时候，如深绿色的点，QAA算法相比于SA算法基本上具有根号加速，当次优解的态空间比较局域的时候，此时重点是看次优解的态空间与最优解的量子态空间的汉明距离的远近，如果汉明距离整体偏小，如图17c中的图1和图2，那么此时QAA还是能够存在加速的效果，但是如果汉明距离很大的时候，QAA算法反而会具有减速的效果。

04

量子绝热优化难实例的超指数运行时间的规避

4.1 量子绝热优化难实例

图18 准1D图（来源：arXiv:2306.13131v1）

图18A中展示了四种准1D的链状图，给链上的每一个位置进行编号，用i表示。根据之前讨论的里德堡相互作用，每一个位置的两个原子可能处于对称子空间的两种量子态和非对称子空间一种量子态的叠加。对于失谐量从负数缓慢扫射到正数的情况，量子态只会在对称子空间中进行演化，因此可以将同一个位置上的两个原子看成是一个二能级系统，拉比频率相应的变化为。选取第四种图开展后面的分析，这种图可以等效于图18C中的图，对应对偶PXP模型，在这种模型中，受到加强的拉比频率的原子相比于普通的原子更容易激发到里德堡态，因此，这种结构相比于演化到MIS问题结果的，更加容易演化到次优解。如图19所示，随着原子数的增加(L增加)，哈密顿量的基态本征能量和第一激发态本征能量的差的最小值呈超指数的规律衰减，这意味着对于最坏的情况，绝热算法想要演化到基态需要的时间。这样的情况，绝热算法的求解效率非常的低。

图19 哈密顿量的基态本征能量和第一激发态本征能量的差的最小值（来源：arXiv:2306.13131v1）

4.2 方法一：改变演化哈密顿量

考虑使用两种方法来解决对于次优解简并过大的情况，演化时间超指数的问题。第一种方法是在演化哈密顿量中添加一些额外的自旋交换项，比如可以使用如下的哈密顿量

其中，不考虑长程相互作用，并且设置。在这种情况下，尽管最小能级间隙仍然是随着N的增大呈超指数衰减。但是正如图20A所示，在演化哈密顿量中加入自旋交换项后，最小能级间隙显著提升。

图20 （来源：arXiv:2306.13131v1）

类似于在哈密顿量中加入自旋交换项，通过加入全局拉普拉斯项可以得到更好的效果，修改后的哈密顿量表示为

其中对于奇数i，对于偶数i，对于。对于比较大的系统，最小间隙能量大约为，对于准一维对偶链状图，次优解的简并

因此，在这种情况下，最小间隙能量与点数的关系变为指数的关系，而不是超指数的关系。

4.3 方法二：使用多体疤痕淬灭相变方法

多体疤痕首先在研究1里德堡链的时候发现，这种现象展示了在全局淬火之后态与态之间的振荡。

图21 E.保真度在和时间测得。(来源：arXiv:2306.13131v1)

量子疤痕动力学在模型中的哈密顿量可以表示为

其中。图16D展示了求解过程，首先通过快速退火的方法得到次优解，然后使用全局淬火，等待系统演化一段时间后测量。这个方法同样可以拓展到2维的简并图。

05

总结

中性原子系统非常适用于解决最大独立集问题。对于难以求解的图，如果次优解的汉明距离相较于最优解的汉明距离不是非常大，相较于经典的模拟量子退火算法，量子的退火算法可以设计演化哈密顿量，从而使得量子算法实现加速的效果。

欢迎专家学者在公众号投稿分享优秀论文和创新成果，投稿录取者可获得精美礼品一份，投稿联系HiQ量子计算小助手：LLT66TT（备注“量子计算专题投稿”） 

欢迎大家订阅“量子计算HiQ”，查看更多论文分享和学术活动信息

量子计算组会一起开

END

期待您成为新时代的开源贡献者，

加入MindSpore Quantum的开发者行列，共同携手推进量子计算新发展！

长按下方二维码加入MindSpore Quantum项目↓

MindSpore Quantum官方资料

Gitee社区：https://gitee.com/mindspore/mindquantum

HiQ官网：https://hiq.huaweicloud.com/tutorial
MindSpore官网：https://www.mindspore.cn/mindquantum/docs/zh-CN/r0.9/index.html

欢迎关注MindSpore Quantum!